The invention relates to data storage. More specifically, the invention relates to modulation encoding of data prior to storage on a recordable medium.
In magnetic and optical memory devices, sectors of user data are typically encoded prior to storage on recordable media. The sectors are arranged into blocks, and the blocks of user data are encoded for forward error correction. Redundancy data such as error correction codewords are added to the user data, thereby forming Error Correction Codeword ("ECC") blocks. The redundancy data allows for forward error correction of user data that, after retrieval, has been found to contain errors (for example, due to an error on the storage medium).
The ECC blocks are then modulation encoded. During modulation encoding, slices of bits (hereinafter referred to as "messages") of the blocks are mapped into distinct symbols. For instance, 8-bit messages might be mapped into distinct 16-bit symbols or codewords. One popular modulation code is a "(2,10)-Run Length Limited" code.
Blocks of these codewords are then written to a storage medium. In the case of a hard drive, the codewords are typically arranged on a platter in concentric tracks. In the case of an optical disc such as a CD or DVD, the data is stored in a spiral groove in a substrate (and perhaps on lands too). In both cases, the data storage is one-dimensional.
Recent proposals for the design of optical storage-in particular holographic memory design-have attempted to take advantage of the fact that the recording surface of the media is actually two-dimensional. Storing data in two dimensions instead of one dimension would allow recording density to be increased.
Adding the additional dimension to encoding, however, introduces new types of constraints on the recorded data. Experiments reported on holographic memory, and experience gathered in other existing optical devices, suggest that the number of 0's and 1's in the recorded data should be balanced within certain areas or patterns. If data is recorded in two-dimensional n.times.m rectangular arrays (that is, arrays having n rows and m columns), one constraint of potential interest requires that every row and column of the recorded array be balanced. A row or column or, more generally, a vector having 0,1 entries is balanced if it has the same number of 0's and 1's. Such arrays shall be referred to as balanced arrays. Thus, the problem becomes one of encoding unconstrained (binary) messages into distinct n.times.m balanced arrays of recorded data.
Lowering the redundancy of the encoding algorithm makes it more efficient since it can represent a greater number of messages using a given array size, and hence a given area on the storage medium. A two-dimensional encoding algorithm for balanced arrays has been proposed in a paper by R. Talyansky, T. Etzion and R. M. Roth in "Efficient code constructions for certain two-dimensional constraints," IEEE Trans. Inform. Theory, 45 (1999), pp. 794-99.
An encoding algorithm that achieves a smaller redundancy would be desirable. Reducing the redundancy would allow a greater number of messages to be packed into n.times.m balanced arrays. This, in turn, would allow more data to be placed on the tracks. Reducing the redundancy would also allow tracks to be spaced closer together. Thus, reducing the redundancy in two dimensions would allow storage density to be increased.